class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle == null  || triangle.size() == 0) {
            return 0;
        }
        if(triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int[][] aa = new int[triangle.size()][triangle.get(triangle.size()-1).size()];
        aa[0][0] = triangle.get(0).get(0);
        for(int i = 1;i < triangle.size();i++) {
            for(int j = 0;j < triangle.get(i).size();j++) {
                if(j == 0) {
                    aa[i][j] = triangle.get(i).get(j) + aa[i-1][j];
                } else if(j == triangle.get(i).size()-1) {
                    aa[i][j] = triangle.get(i).get(j) + aa[i-1][j-1];
                } else {
                    aa[i][j] = triangle.get(i).get(j) + Math.min(aa[i-1][j-1],aa[i-1][j]);
                }
            }
        }
        int min = aa[aa.length-1][0];
        for(int i = 1;i < aa[0].length;i++) {
            min = Math.min(min,aa[triangle.size()-1][i]);
        }
        return min;
    }
}